package pers.sloera.leetcode.editor.cn;//给定一个按照升序排列的整数数组 nums，和一个目标值 target。找出给定目标值在数组中的开始位置和结束位置。
//
// 如果数组中不存在目标值 target，返回 [-1, -1]。 
//
// 进阶： 
//
// 
// 你可以设计并实现时间复杂度为 O(log n) 的算法解决此问题吗？ 
// 
//
// 
//
// 示例 1： 
//
// 
//输入：nums = [5,7,7,8,8,10], target = 8
//输出：[3,4] 
//
// 示例 2： 
//
// 
//输入：nums = [5,7,7,8,8,10], target = 6
//输出：[-1,-1] 
//
// 示例 3： 
//
// 
//输入：nums = [], target = 0
//输出：[-1,-1] 
//
// 
//
// 提示： 
//
// 
// 0 <= nums.length <= 10⁵ 
// -10⁹ <= nums[i] <= 10⁹ 
// nums 是一个非递减数组 
// -10⁹ <= target <= 10⁹ 
// 
// Related Topics 数组 二分查找 👍 1552 👎 0


//leetcode submit region begin(Prohibit modification and deletion)
class Solution34 {
    // public static void main(String[] args) {
    //   final Solution34 solution2 = new Solution34();
    //   final int[] x = solution2.searchRange(new int[]{5, 7, 7, 8, 8, 10}, 6);
    //   System.out.println(x);
    // }
    public int[] searchRange(int[] nums, int target) {
        final int[] ret = {-1, -1};
        if (nums.length == 0) {
            return ret;
        }
        if (nums.length == 1) {
            if (nums[0] == target) {
                return new int[]{0, 0};
            } else {
                return ret;
            }
        }
        int middle = findTarget(nums, 0, nums.length - 1, target);
        if (middle == -1) {
            return ret;
        }
        // left
        for (int i = middle; i >= 0; i--) {
            if (nums[i] == target) {
                ret[0] = i;
            } else {
                break;
            }
        }
        // right
        for (int i = middle; i < nums.length; i++) {
            if (nums[i] == target) {
                ret[1] = i;
            } else {
                break;
            }
        }
        return ret;
    }

    /**
     * 使用二分从nums中找寻target
     *
     * @param target 目标值
     * @return int 如果未找到，返回-1
     * @date 2022/3/22
     */
    private int findTarget(int[] nums, int left, int right, int target) {
        if (left == right) {
            if (nums[left] == target) {
                return left;
            } else {
                return -1;
            }
        }
        if (right - left == 1) {
            if (nums[left] == target) {
                return left;
            } else if (nums[right] == target) {
                return right;
            } else {
                return -1;
            }
        }
        int middle = (left + right) >> 1;
        if (nums[middle] == target) {
            return middle;
        } else if (nums[middle] < target) {
            return findTarget(nums, middle, right, target);
        } else {
            return findTarget(nums, left, middle, target);
        }
    }
}
//leetcode submit region end(Prohibit modification and deletion)
